The present invention relates generally to packet communication systems and telecommunication networks. In particular, the present invention relates to rerouting or reorganizing the path of a connection within a connection-oriented packet network such as an asynchronous transfer mode (ATM) network or a frame relay network.
Modern digital communications often use packet switching connection oriented networks of which Asynchronous Transfer Mode (ATM) networks are an important example. In packet switching connection oriented networks, a user digital data stream is broken into discrete units (for example of 48 bytes each). Each such unit is transmitted in a packet (or cell in the case of ATM). Attached to the front of the user data portion of the packet is certain header information. This header information includes fields used by the switches of the packet switching network to identify the correct rule for switching the packet; that is, to move the packet from the particular links or transmission facility from which the packet enters the switch to the particular transmission facility upon which the packet will be transmitted out of the switch. In the context of an ATM network, the VPI (Virtual Path Identifier) and VCI (Virtual Channel Identifier) fields (sometimes only the VPI field is used) in the ATM cell header (see FIG. 1) provide this functionality. Before transmitting the packets out of the switch, the switch generally modifies these header field values to align with the control data that will be used by the adjacent downstream switch to further switch the packet or to align with the expectations of the recipient of the data. Since this invention relates to connection oriented networks, all packets belonging to the same data stream, for example, the same telephone voice call, same fax transmission, or same data file download, will all traverse the same path through the network. That is, all packets belonging to the same data steam or call will traverse the same set of switches, use the same links between adjacent pairs of those switches, and upon each such links, use the same header index values. In support of the connection over the path, each participating switch will have stored rules that tell it how to map a packet arriving on a particular facility to a particular out-going facility and how to translate the relevant header routing indices. These rules are determined and come to be stored in the switches along the path of the connection by means of either signaling messages or via provisioning management, or some combination of the two.
To make the explanation more specific, we will refer to ATM connections. Hence packets are referred to as cells and the header routing indices are referred to as the VPI/VCI values. The applicability of the invention to packet switched connection oriented networks other than ATM networks is straightforward.
In a connection oriented packet network such as an Asynchronous Transfer Mode (ATM), or frame relay network, a connection (e.g., an ATM Permanent Virtual Circuit) (PVC) may need be moved to a replacement path despite the fact that the existing path is operational. This invention provides a means for executing that move to a replacement path without the loss, duplication, or mis-ordering of packets (cells). We first explain how the need to move a connection from a working path to a replacement path might arise. Next we explain how differences in cell delay along the original versus replacement path make it difficult to guarantee that the change in path does not cause lost, duplicate, or out-of-order cells.
It may happen that a network administrator wants to move a working connection from an existing path to a some other path, herein termed the replacement path. There could be many motivations for doing this. For example, the existing path may be undesirable because it involves excessively many links or uses congested links. (An example of how such a situation could arise is as follows: Assume the connection was initially created on path A. Due to link failure on path A, the connection needed to be moved, on an emergency basis, to a replacement path B. Given the emergency situation, the network could not expend the time to find an optimum path, and accepted a path B that may be excessively long, congested, or some other way inconsistent with the connection""s quality of service expectations or proper allocation of network resources among connections. By and by, the failure that precipitated the emergency change in path from A to B is corrected. Then, the network administrator may wish to return the connection from the use of path B to A or to some third path that is superior to B. This change from the working path B to a replacement path generally need not be done on an emergency basis, but should be done xe2x80x9csooner or laterxe2x80x9d to improve the performance of the connection or reduce the network resources (e.g. number of links) allocated to the connection.) On the other hand, the motivation for moving a working connection to a new path may be simply to better balance the load on the network.
Solution
Applicant will first analyze the problem in order to derive the proposed solution.
In the context of moving a connection from one path (the existing path) to another path, (the replacement path) we refer to the switch at which the two paths diverge as the originating switch, and we refer to the switch at which the two paths again converge as the destination switch. This terminology assumes a focus upon one direction of cell flow. The methods we discuss for changing a connection""s path are described in terms of only one direction of flow. However, the actual implementation would apply these methods to each direction of a bidirectional flow with the role of the xe2x80x9coriginating switchxe2x80x9d and xe2x80x9cdestination switchxe2x80x9d reversed. Note that the replacement and original path may share some common links (i.e. facilities) , but over those links different header indexes (VPI/VCI for ATM) would be used to distinguish cells assigned the respective paths.
To understand why moving a connection from one path to another may result in lost, duplicated, or out-of-order cells, first note that the time it takes a cell to leave an ATM switch and travel along a path involving many ATM switches until it arrives at the destination ATM switch will depend upon the path taken between the originating and destination ATM switch. If we change the path taken (perhaps changing the set of intermediate ATM switches, perhaps only the links used between adjacent ATM switches, perhaps some combination of the two kinds of changes), the delay experienced by cells will generally change. Two elements contribute to this difference in delay. The first is propagation delay, the time cells spend traversing links, since the paths may differ in the number of links traversed and the length (and/or propagation speed) of those links. The second is buffering delay, the total time cells spend stored within (not between) the switches along the path. The paths may differ in buffering delay, which is a function of the cell flow of many connections besides the one of interest to us, encountered within the ATM switches involved in the connection. Even if the two paths use the same set of switches, different queues may be used in those switches for the different links used in the two paths. To further complicate the situation, we may not be able to definitively label one of the two paths as the faster of the two, since the delay in particular queues can change moment to moment. The delay experienced in a queue depends upon the characteristics of the several connections using that queue, and different queues serve different sets of connections with different traffic patterns. So the identity of the xe2x80x9cfaster pathxe2x80x9d may change from moment to moment if the variation in buffering cell delay is large relative to the difference in transmission delay between the two paths. Note that the invention described herein does not rely on any particular relationship between path length and delay; nor does it rely upon one path or the other consistently providing less delay.
When moving a connection from one working path to another, this differential delay between the original and the replacement path can damage the integrity of the cell stream as will be explained below. It is the purpose of this invention to prevent this damage. Observe what happens when the originating node stops sending cells on the original path and starts (with the next cell) sending cells on the replacement path. Some of the cells sent on the replacement path may arrive at the destination switch before some of the cells launched onto the original path arrive there. If the destination switch transmits cells it receives for the connection in the order it receives those cells, then the sequential order of the cell stream may be corrupted. (Note: we will say xe2x80x9ctransmits cellsxe2x80x9d as a short hand when referring to the destination switch placing the cells upon the output queue for the outgoing port or placing the cells in a shaping function for transmission on the outgoing port). On the other hand, if the destination switch follows the policy of discarding any cells received on the original path once it has received a cell on the replacement path, then any cells still in transit along the original path will be lost.
The integrity of the cell stream is also damaged when an alternative path switchover uses a cell replication technique. The originating switch replicates the cells of the connection and sends a copy of each cell on the original and replacement path. Then the destination switch, at some subsequent time, begins discarding cells arriving on the original path and transmitting cells arriving on the replacement path. But again, the differential delay along the two paths can cause difficulties. When the destination switch starts transmitting cells arriving from the replacement path, copies of some of those cells may already have been received on the original path and transmitted. This means duplicate copies of some cells are delivered to the destination. On the other hand, when the destination node starts using the replacement path as its source for cells to transmit, the replacement path copies of cells belonging after the last cell accepted from the original path may already have been received on the replacement path and discarded. Any such cells will be missing from the stream delivered to the output port.
The above has analyzed a problem of the prior art, namely that the differential delay with respect to original and replacement paths can result in out-of-order, duplicated, or missing cells in the cell stream delivered to the ultimate destination when a connection is moved from one path to another.
In accordance with this invention, a system and method is disclosed for rerouting or reorganizing the path of a connection within a connection oriented packet switching network, without incurring the loss, duplication or mis-ordering of data packets or cells when the path of a connection across a network is changed to a superior path (e.g. a path that is shorter, less congested, or whose use better balances network load.)
In one embodiment of the method, the originating switch replicates the cell stream so that one copy continues to follow the original path and the second copy follows the replacement path. Then, at some point upstream from where this replication is carried out, a special marker cell is created and inserted into the cell steam. As a result of these actions, two identical copies of the cell stream flow from the originating switch to the destination switch and the marker cell is identically positioned in the respective cell streams. The destination switch initially continues to transmit only cells arriving at it on the original path, but it commences to monitor the cells arriving on both the original and replacement path for the arrival of the marker. Data cells arriving on the original path prior to the marker arriving within that path, will be transmitted by the destination switch. Data cells arriving on the replacement path after the replacement path marker will, after a possible period of buffering, be transmitted from the destination switch. Temporary buffering will be needed for any cells arriving on the replacement path after the replacement path marker but before the arrival of the original path marker. These cells are transmitted upon the arrival of the original path marker.
The second embodiment of the invention does not involve replication of the cell stream. Instead, the originating switch diverts the cell stream from the original path to the replacement path after sending some arbitrarily selected last customer data cell along the original path. All subsequent data cells are sent along the replacement path. However, a special marker cell is created at the originating switch and sent along the original path to follow the last customer data cell using the original path. A marker cell may optionally be sent along the replacement path preceding the first data cell to be sent on that path. The behavior of the destination switch is similar to the case above, except that if a marker is not used on the replacement path, the destination switch acts as if such a marker had arrived before the first arriving data cell on that path.
Both embodiments of the invention require some message communication between the originating and destination switch to coordinate their actions. The marker cell can be a cell specially created for this purpose which would not be transmitted from the destination switch. Alternatively, the marker cell can be a data cell with its header somehow marked to indicate its purpose and which would be transmitted by the destination switchxe2x80x94perhaps after removing the distinctive modification to its header.
These procedures guarantee that the data stream can be transferred from the original to the replacement network path without any loss, duplication, or mis-ordering of the data cells despite differences in the delay experienced by cells along the respective paths.
A rerouting or reorganizing of a connection could be initiated by either a network administrator or by automated network administration. The method applies to both uni-directional or bi-directional connections, but for simplicity only the uni-directional is described. The bi-directional case basically involves using the uni-directional method for each of the two directions of flow. Two primary embodiments of the method will be discussed.
With respect to the direction of data flow considered, the switch where the two paths diverge is herein termed the origination switch and the switch where the two path again converge is herein termed the destination switch. (For the reverse direction of data flow, the roles of these two switches is essentially reversed). Special actions need to be taken at both the origination and the destination switches in a coordinated way to execute the seamless changeover.